package com.LeeCode;

/**
 * 滑动子数组的美丽值
 */

public class Code2653 {
    public static void main(String[] args) {

    }

    public int[] getSubarrayBeauty(int[] nums, int k, int x) {
        int[] result = new int[nums.length - k + 1];
        int[] count = new int[101]; // Maps -50 to 50 into 0 to 100

        // Initialize the first window
        for (int i = 0; i < k; i++) {
            count[nums[i] + 50]++;
        }
        result[0] = getXthSmallest(count, x);

        for (int i = 1; i <= nums.length - k; i++) {
            // Remove the leftmost element
            count[nums[i - 1] + 50]--;
            // Add the new right element
            count[nums[i + k - 1] + 50]++;
            // Compute the beauty for the current window
            result[i] = getXthSmallest(count, x);
        }

        return result;
    }

    private int getXthSmallest(int[] count, int x) {
        int cnt = 0;
        for (int num = 0; num <= 100; num++) {
            cnt += count[num];
            if (cnt >= x) {
                int originalNum = num - 50;
                return originalNum < 0 ? originalNum : 0;
            }
        }
        return 0;
    }
}
